package top.lywivan.heap;

import java.util.Arrays;

/**
 * @author :lyw.ivan
 * @date :Created in 2022/7/9
 * @description : 二叉大顶堆
 * @version: 1.0
 */
public class BigTopHeap {
    //定义完全二叉树
    private int[] fullBinaryTree;

    //数组容量
    private int capacity;

    //节点数量
    private int size;

    public BigTopHeap(){
        this.capacity=10;
        this.fullBinaryTree=new int[capacity];
    }

    /**
     * 插入元素
     * @param val
     */
    public void insert(int val){
        if(size+1>capacity){
            grow(capacity+1);
        }
        fullBinaryTree[size]=val;
        //heapifyUp
        for(int curr=size;curr>0;curr=(curr-1)/2){
            //找到父节点
            int par=fullBinaryTree[(curr-1)/2];
            //比较
            if(par<fullBinaryTree[curr]){
                //需要进行交换
                fullBinaryTree[(curr-1)/2]=fullBinaryTree[curr];
                fullBinaryTree[curr]= par;
            }else {
                break;
            }
        }
        size++;
    }

    /**
     * 移除最大元素
     * @return
     */
    public int removeMax(){
        if (size<1){
            return 0;
        }
        int max=fullBinaryTree[0];
        //heapifyDown
        //替换堆顶和堆尾元素
        fullBinaryTree[0]=fullBinaryTree[size-1];
        for (int curr=0;2*curr+1<size;){
            //获取左右子节点
            int left=2*curr+1;
            int right=2*curr+2<size?2*curr+2:left;
            if(fullBinaryTree[curr]<fullBinaryTree[left]||fullBinaryTree[curr]<fullBinaryTree[right]){
                if(fullBinaryTree[left]<fullBinaryTree[right]){
                    int temp=fullBinaryTree[right];
                    fullBinaryTree[right]=fullBinaryTree[curr];
                    fullBinaryTree[curr]=temp;
                    curr=right;
                }else {
                    int temp=fullBinaryTree[left];
                    fullBinaryTree[left]=fullBinaryTree[curr];
                    fullBinaryTree[curr]=temp;
                    curr=left;
                }
            }else {
                break;
            }
        }
        size--;
        return max;
    }

    /**
     * 获取最大值
     * @return
     */
    public int getMax(){
        if(size>0){
            return fullBinaryTree[0];
        }else {
            return 0;
        }
    }

    private void grow(int newCapacity) {
        int oldCapacity=capacity;
        if(newCapacity<(oldCapacity+oldCapacity>>2)){
            newCapacity=oldCapacity+oldCapacity>>2;
        }
        capacity=newCapacity;
        int[] newArray=new int[newCapacity];
        System.arraycopy(fullBinaryTree,0,newArray,0,capacity);
        fullBinaryTree=newArray;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < size; i++) {
            sb.append(fullBinaryTree[i]).append("->");
        }
        return sb.toString();
    }
}
